import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-08-21
 * Time: 18:54
 */

/**
 * 和为S的两个数字:
 * 双指针
 * 描述
 * 输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。
 *
 * 示例1
 * 输入：
 * [1,2,4,7,11,15],15
 * 复制
 * 返回值：
 * [4,11]
 * 复制
 * 说明：
 * 返回[4,11]或者[11,4]都是可以的
 * 示例2
 * 输入：
 * [1,5,11],10
 * 复制
 * 返回值：
 * []
 * 复制
 * 说明：
 * 不存在，返回空数组
 * 示例3
 * 输入：
 * [1,2,3,4],5
 * 复制
 * 返回值：
 * [1,4]
 * 复制
 * 说明：
 * 返回[1,4],[4,1],[2,3],[3,2]都是可以的
 * 示例4
 * 输入：
 * [1,2,2,4],4
 * 复制
 * 返回值：
 * [2,2]
 */
public class SumExercise {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        /**
         利用双指针算法和单调性解决
         */
        ArrayList<Integer> list = new ArrayList<>();
        int left = 0;
        int right = array.length-1;
        while(left < right) {

            if(array[left] + array[right] > sum) {
                right--;
            }else if(array[left] + array[right] < sum){
                left++;
            }else {
                list.add(array[left]);
                list.add(array[right]);
                break;
            }
        }

        return list;
    }
}
